'''
Created on 25 2012

@author: noako
'''

from collections import deque
from math import atan2, pi
from FuzzyFloat import FuzzyFloat
from GeometryHelper import Point, AngleBetween

class DCEL:
    def __init__(self, speedy_vertices):
        # initializes the DCEL with one polygon.
        # assume vertices are in counter clockwise order around polygon
        
        inner_f = Face()
        outer_f = Face()
        self.faces = [inner_f, outer_f]

        self.vertices = [Vertex(p) for (p,s) in speedy_vertices]
        #create the inner edges
        inner_edges = [HalfEdge(v, s) for (v,(p,s)) in zip(self.vertices, speedy_vertices)]
        #create the outer edges (without speeds)
        outer_edges = deque([HalfEdge(v) for v in self.vertices])
        
        #link each vertex to the inner edge that goes out of it
        for v, h in zip(self.vertices, inner_edges):
            v.incident_edge = h
            
        outer_edges.rotate(-1) #now twins are facing each other            
        #link Between twins
        for inner,outer in zip(inner_edges, outer_edges) :
            inner.twin = outer
            outer.twin = inner
        
        #set nexts, prevs and face
        for i, inner in enumerate(inner_edges):
            inner.prev = inner_edges[i - 1]
            inner_edges[i - 1].next = inner
            inner.face = inner_f
        for i, outer in enumerate(outer_edges):
            outer.next = outer_edges[i - 1]
            outer_edges[i - 1].prev = outer
            outer.face = outer_f
        
        #set inner and outer components    
        inner_f.outer_component = inner_edges[0]
        inner_f.inner_components = []
        outer_f.outer_component = None
        outer_f.inner_components = [outer_edges[0]]
        
        outer_edges.extend(inner_edges)
        self.edges = outer_edges
            
    def CreateEdge(self, v1, v2):
        #create edge Between two existing vertices. Updates other edges as needed
        #this is only called to create new skeleton edges (not polygon edges), thus they don't have speed
        assert(v1.incident_edge != None or v2.incident_edge != None) #graph edges should always be connected
        need_split = (v1.incident_edge != None and v2.incident_edge != None)
            
        h1 = HalfEdge(v1)
        h2 = HalfEdge(v2)
        self.edges.extend([h1, h2])
        h1.twin = h2
        h2.twin = h1
        ConnectAtVertex(v1, h1)
        ConnectAtVertex(v2, h2)
        if need_split:
            #need to split a face
            f = h1.next.face
            h1.face = f
            f_new = Face()
            self.faces.append(f_new)
            f_new.outer_component = h2
            
            h = h2
            h.face = f_new
            while h != h2:
                h.face = f_new
                h = h.next

    def CreateVertex(self, point):
        v = Vertex(point)
        self.vertices.append(v)
        return v

    def GetInnerPolygonEdge(self):
        for face in self.faces:
            if face.outer_component != None:
                return face.outer_component       
            
    def center(self,min_width, min_height):
        for vertex in self.vertices:
            vertex.point = Point(vertex.point.x-min_width,vertex.point.y-min_height)
           
    def moveBy(self,num):
        for vertex in self.vertices:
            vertex.point = Point(vertex.point.x+num,vertex.point.y+num) 
            
    def scale(self,min_width, max_width):
        factor = 1
        while  max_width-min_width < 100 :
            factor = factor*10
            max_width = max_width*10
            min_width = min_width*10 
        while  max_width-min_width > 1000 :
            factor = float (factor/10.0)
            max_width = float (max_width/10.0)
            min_width = float(min_width/10.0)
        for vertex in self.vertices:
            vertex.point = Point(vertex.point.x*factor,vertex.point.y*factor)
        return factor
            
         
class Vertex:
    def __init__(self, point):
        self.point = point
        self.incident_edge = None
    
    def __repr__(self):
        return str(self.point)

class HalfEdge:
    def __init__(self, origin, speed=0):
        self.origin = origin
        self.speed = speed
        self.next = None
        self.prev = None
        self.twin = None
        self.face = None        

    def destination(self):
        return self.twin.origin

    def __repr__(self):
        return str(self.origin) + '->' + str(self.destination())

    def angle(self):
        #returns the angle of the half edge relative to the x axis in radians, between -pi and pi
        o = self.origin.point
        d = self.destination().point
        return FuzzyFloat(atan2(d.y - o.y, d.x - o.x)) #return an angle Between -pi and pi

class Face:
    def __init__(self):
        self.outer_component = None
        self.inner_components = []

def ConnectAtVertex(v, h):
    #find the two existing edges adjacant to v1 that this new edge is wedged Between
    if v.incident_edge == None:
        v.incident_edge = h
        h.prev = h.twin
        h.twin.next = h
        return
    h1 = v.incident_edge
    if h1.prev == h1.twin:
        #v has only one adjacant edge
        h2 = h1
    else:
        h2 = h1.prev.twin
        while not AngleBetween(h1.angle(), h.angle(), h2.angle()):
            h1 = h2
            h2 = h1.prev.twin
    h1.prev = h.twin
    h.twin.next = h1
    h2.twin.next = h        
    h.prev = h2.twin

